/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-07
 * Time: 10:41
 */


class Solution {
    //21.合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }

    //206.反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
    //24.两两交换链表中的结点
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = swapPairs(head.next.next);
        ListNode ret = head.next;
        head.next.next = head;
        head.next = cur;
        return ret;
    }

    //50.Pow(x,n)
    public double myPow(double x, int n) {
        long N = n;
        //负无穷会超出范围
        return N < 0 ? 1.0 / pow(x,-N) : pow(x,N);
    }

    public double pow(double x ,long n) {
        if(n == 0) {
            return 1.0;
        }
        double tmp = pow(x,n/2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
}
